/**
 * 层序遍历，每层遍历时给出队列的节点挂载 next，并让 next 等于队列中头部节点（queue[0]）
 * @param {Node} root
 * @return {Node}
 */
const connect = root => {
  if (!root) return root
  const queue = [root]
  while (queue.length) {
    const len = queue.length
    for (let i = 0; i < len; i++) {
      const node = queue.shift()
      if (i < len - 1) {
        node.next = queue[0]
      }
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }
  }
  return root
}

const root = {
  val: 1,
  left: {
    val: 2,
    left: null,
    right: null
  },
  right: {
    val: 3,
    left: null,
    right: null
  }
}

console.log(connect(root))